SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Random binary tree</title>

</head>

Random binary tree

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a> and <a href="Probability_theory" title="Probability theory">probability theory</a>, a random binary tree is a <a href="Binary_tree" title="Binary tree">binary tree</a> selected at random from some <a href="Probability_distribution" title="Probability distribution">probability distribution</a> on binary trees. Different distributions have been used, leading to different properties for these trees.

Random binary trees have been used for analyzing the <a href="Average-case_complexity" title="Average-case complexity">average-case complexity</a> of <a href="Data_structure" title="Data structure">data structures</a> based on <a href="Binary_search_tree" title="Binary search tree">binary search trees</a>. For this application it is common to use random trees formed by inserting nodes one at a time according to a <a href="Random_permutation" title="Random permutation">random permutation</a>.<a href="#cite_note-FOOTNOTEDrmota200919-1">[1]</a> The resulting trees are very likely to have logarithmic depth and logarithmic <a href="Strahler_number" title="Strahler number">Strahler number</a>. The <a href="Treap" title="Treap">treap</a> and related <a href="Balanced_binary_search_tree" class="mw-redirect" title="Balanced binary search tree">balanced binary search trees</a> use update operations that maintain this random structure even when the update sequence is non-random.

Other distributions on random binary trees include the <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">uniform discrete distribution</a> in which all distinct trees are equally likely, distributions on a given number of nodes obtained by repeated splitting, binary <a href="Trie" title="Trie">tries</a> and <a href="Radix_tree" title="Radix tree">radix trees</a> for random data, and trees of variable size generated by <a href="Branching_process" title="Branching process">branching processes</a>.

For random trees that are not necessarily binary, see <a href="Random_tree" title="Random tree">random tree</a>.

<div class="mw-heading mw-heading2"><h2 id="Background">Background</h2></div>

A binary tree is a <a href="Rooted_tree" class="mw-redirect" title="Rooted tree">rooted tree</a> in which each node may have up to two children (the nodes directly below it in the tree), and those children are designated as being either left or right. It is sometimes convenient instead to consider extended binary trees in which each node is either an external node with zero children, or an internal node with exactly two children. A binary tree that is not in extended form may be converted into an extended binary tree by treating all its nodes as internal, and adding an external node for each missing child of an internal node. In the other direction, an extended binary tree with at least one internal node may be converted back into a non-extended binary tree by removing all its external nodes. In this way, these two forms are almost entirely equivalent for the purposes of mathematical analysis, except that the extended form allows a tree consisting of a single external node, which does not correspond to anything in the non-extended form. For the purposes of computer data structures, the two forms differ, as the external nodes of the first form may be represented explicitly as objects in a data structure.<a href="#cite_note-FOOTNOTEKnuth1997-2">[2]</a>

In a <a href="Binary_search_tree" title="Binary search tree">binary search tree</a> the internal nodes are labeled by numbers or other ordered values, called keys, arranged so that an <a href="Inorder_traversal" class="mw-redirect" title="Inorder traversal">inorder traversal</a> of the tree lists the keys in sorted order. The external nodes remain unlabeled.<a href="#cite_note-FOOTNOTEKnuth1973-3">[3]</a> Binary trees may also be studied with all nodes unlabeled, or with labels that are not given in sorted order. For instance, the <a href="Cartesian_tree" title="Cartesian tree">Cartesian tree</a> data structure uses labeled binary trees that are not necessarily binary search trees.<a href="#cite_note-FOOTNOTEVuillemin1980-4">[4]</a>

A random binary tree is a random tree drawn from a certain <a href="Probability_distribution" title="Probability distribution">probability distribution</a> on binary trees. In many cases, these probability distributions are defined using a given set of keys, and describe the probabilities of binary search trees having those keys. However, other distributions are possible, not necessarily generating binary search trees, and not necessarily giving a fixed number of nodes.<a href="#cite_note-FOOTNOTESedgewickFlajolet2013286-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="From_random_permutations">From random permutations</h2></div>

For any sequence of distinct ordered keys, one may form a <a href="Binary_search_tree" title="Binary search tree">binary search tree</a> in which each key is inserted in sequence as a leaf of the tree, without changing the structure of the previously inserted keys. The position for each insertion can be found by a <a href="Binary_search" title="Binary search">binary search</a> in the previous tree. The random <a href="Permutation_model" title="Permutation model">permutation model</a>, for a given set of keys, is defined by choosing the sequence randomly from the <a href="Permutation" title="Permutation">permutations</a> of the set, with each permutation having equal probability.<a href="#cite_note-FOOTNOTEMorin2014-6">[6]</a>

For instance, if the three keys 1,3,2 are inserted into a binary search tree in that sequence, the number 1 will sit at the root of the tree, the number 3 will be placed as its right child, and the number 2 as the left child of the number 3. There are six different permutations of the keys 1,2, and 3, but only five trees may be constructed from them. That is because the permutations 2,1,3 and 2,3,1 form the same tree. Thus, this tree has probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {2}{6}}={\tfrac {1}{3}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {2}{6}}={\tfrac {1}{3}}}</annotation>

</semantics>

</math><img src="./9040c468c49aa0e18e4d245679a4f5f8fca0a015.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.415ex; height:3.676ex;" alt="{\displaystyle {\tfrac {2}{6}}={\tfrac {1}{3}}}" loading="lazy"> of being generated, whereas the other four trees each have probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{6}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{6}}}</annotation>

</semantics>

</math><img src="./5bc02e655226b1a0e18922e932efff50531c48eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:1.658ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{6}}}" loading="lazy">.<a href="#cite_note-FOOTNOTESedgewickFlajolet2013286-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="Expected_depth_of_a_node">Expected depth of a node</h3></div>

For any key <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in a given set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> keys, the <a href="Expected_value" title="Expected value">expected value</a> of the length of the path from the root to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in a random binary search tree is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\log n+O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\log n+O(1)}</annotation>

</semantics>

</math><img src="./919232a4cea985c2cf978fc0b3084eaab66445a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.889ex; height:2.843ex;" alt="{\displaystyle 2\log n+O(1)}" loading="lazy">, where "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log }</annotation>

</semantics>

</math><img src="./79e4debd0ab1c6ce342d0172a7643733305c37bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.972ex; height:2.509ex;" alt="{\displaystyle \log }" loading="lazy">" denotes the <a href="Natural_logarithm" title="Natural logarithm">natural logarithm</a> function and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O}</annotation>

</semantics>

</math><img src="./9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="{\displaystyle O}" loading="lazy"> introduces <a href="Big_O_notation" title="Big O notation">big O notation</a>. By <a href="Linearity_of_expectation" class="mw-redirect" title="Linearity of expectation">linearity of expectation</a>, the expected number of ancestors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> equals the sum, over other keys <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, of the probability that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is an ancestor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. A key <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is an ancestor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> exactly when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> is the first key to be inserted from the interval <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [x,y]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [x,y]}</annotation>

</semantics>

</math><img src="./1b7bd6292c6023626c6358bfd3943a031b27d663.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.813ex; height:2.843ex;" alt="{\displaystyle [x,y]}" loading="lazy">. Because each key in the interval is equally likely to be first, this happens with probability inverse to the length of the interval. Thus, the keys that are adjacent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in the sorted sequence of keys have probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./edef8290613648790a8ac1a95c2fb7c3972aea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}}" loading="lazy"> of being an ancestor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, the keys one step away have probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{3}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{3}}}</annotation>

</semantics>

</math><img src="./9efc37d09854a3f8fb997e7de4331876bc49c2c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:1.658ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{3}}}" loading="lazy">, etc. The sum of these probabilities forms two copies of the <a href="Harmonic_series_(mathematics)" title="Harmonic series (mathematics)">harmonic series</a> extending away from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in both directions in the sorted sequence, giving the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\log n+O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\log n+O(1)}</annotation>

</semantics>

</math><img src="./919232a4cea985c2cf978fc0b3084eaab66445a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.889ex; height:2.843ex;" alt="{\displaystyle 2\log n+O(1)}" loading="lazy"> bound above. This bound also holds for the expected search path length for a value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> that is one of the given keys.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading3"><h3 id="The_longest_path">The longest path</h3></div>

The longest root-to-leaf path, in a random binary search tree, is longer than the expected path length, but only by a constant factor. Its length, for a tree with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes, is <a href="With_high_probability" title="With high probability">with high probability</a> approximately

/* start https://en.wikipedia.org/ */

.mw-parser-output .block-indent{padding-left:3em;padding-right:0;overflow:hidden}

/* end https://en.wikipedia.org/ */

</style><div class="block-indent" style="padding-left: 1.6em;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,}</annotation>

</semantics>

</math><img src="./d52db38a73dcf55efc62960e8da76f43ecb8ce05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:21.491ex; height:5.676ex;" alt="{\displaystyle \displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,}" loading="lazy"></div>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> is the unique number in the range <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<\beta <1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<\beta <1}</annotation>

</semantics>

</math><img src="./5823463cddbbeea88e7e3a68c879cc6f391f7e4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.854ex; height:2.509ex;" alt="{\displaystyle 0<\beta <1}" loading="lazy"> satisfying the equation

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle 2\beta e^{1-\beta }=1.}</annotation>

</semantics>

</math><img src="./a20c249374fd0da069eba7a019dcfb17d6f2fe79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.76ex; height:3.009ex;" alt="{\displaystyle \displaystyle 2\beta e^{1-\beta }=1.}" loading="lazy"><a href="#cite_note-8">[8]</a></div>

<div class="mw-heading mw-heading3"><h3 id="Expected_number_of_leaves">Expected number of leaves</h3></div>

In the random permutation model, each key except the smallest and largest has probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{3}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{3}}}</annotation>

</semantics>

</math><img src="./9efc37d09854a3f8fb997e7de4331876bc49c2c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:1.658ex; height:3.676ex;" alt="{\displaystyle {\tfrac {1}{3}}}" loading="lazy"> of being a leaf in the tree. This is because it is a leaf when it inserted after its two neighbors, which happens for two out of the six permutations of it and its two neighbors, all of which are equally likely. By similar reasoning, the smallest and largest key have probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./edef8290613648790a8ac1a95c2fb7c3972aea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}}" loading="lazy"> of being a leaf. Therefore, the expected number of leaves is the sum of these probabilities, which for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq 2}</annotation>

</semantics>

</math><img src="./e6bf67f9d06ca3af619657f8d20ee1322da77174.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 2}" loading="lazy"> is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n+1)/3}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n+1)/3}</annotation>

</semantics>

</math><img src="./03b87bd99f2961831837cb4fce193cfc7a2fe0d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.532ex; height:2.843ex;" alt="{\displaystyle (n+1)/3}" loading="lazy">.<a href="#cite_note-FOOTNOTEBrownShubert1984-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Strahler_number">Strahler number</h3></div>

The <a href="Strahler_number" title="Strahler number">Strahler number</a> of vertices in any tree is a measure of the complexity of the subtrees under those vertices. A leaf (external node) has Strahler number one. For any other node, the Strahler number is defined recursively from the Strahler numbers of its children. In a binary tree, if two children have different Strahler numbers, the Strahler number of their parent is the larger of the two child numbers. But if two children have equal Strahler numbers, their parent has a number that is greater by one. The Strahler number of the whole tree is the number at the root node. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-node random binary search trees, simulations suggest that the expected Strahler number is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{3}n+O(1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{3}n+O(1)}</annotation>

</semantics>

</math><img src="./aab5cee33d298f52275340bdeab6d224994e07dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.393ex; height:2.843ex;" alt="{\displaystyle \log _{3}n+O(1)}" loading="lazy">. A weaker upper bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{3}n+o(\log n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{3}n+o(\log n)}</annotation>

</semantics>

</math><img src="./bcfec04f718ebd55d7918ec7d6be53bee7cb8924.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.339ex; height:2.843ex;" alt="{\displaystyle \log _{3}n+o(\log n)}" loading="lazy"> has been proven.<a href="#cite_note-FOOTNOTEKruszewski1999-10">[10]</a>

<div class="mw-heading mw-heading3"><h3 id="Treaps_and_randomized_binary_search_trees">Treaps and randomized binary search trees</h3></div>

In applications of binary search tree data structures, it is rare for the keys to be inserted without deletion in a random order, limiting the direct applications of random binary trees. However, algorithm designers have devised data structures that allow arbitrary insertions and deletions to preserve the property that the shape of the tree is random, as if the keys had been inserted randomly.<a href="#cite_note-treap-11">[11]</a>

If a given set of keys is assigned numeric priorities (unrelated to their values), these priorities may be used to construct a <a href="Cartesian_tree" title="Cartesian tree">Cartesian tree</a> for the numbers, the binary search tree that would result from inserting the keys in priority order. By choosing the priorities to be independent random real numbers in the unit interval, and by maintaining the Cartesian tree structure using <a href="Tree_rotation" title="Tree rotation">tree rotations</a> after any insertion or deletion of a node, it is possible to maintain a data structure that behaves like a random binary search tree. Such a data structure is known as a <a href="Treap" title="Treap">treap</a> or a randomized binary search tree.<a href="#cite_note-treap-11">[11]</a>

Variants of the treap including the zip tree and zip-zip tree replace the tree rotations by "zipping" operations that split and merge trees, and that limit the number of random bits that need to be generated and stored alongside the keys. The result of these optimizations is still a tree with a random structure, but one that does not exactly match the random permutation model.<a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading2"><h2 id="Uniformly_random_binary_trees">Uniformly random binary trees</h2></div>

The number of binary trees with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes is a <a href="Catalan_number" title="Catalan number">Catalan number</a>.<a href="#cite_note-FOOTNOTEDrmota200926-13">[13]</a> For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1,2,3,\dots }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1,2,3,\dots }</annotation>

</semantics>

</math><img src="./b207567215497887a3250644b8876c23dc3ebf10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.806ex; height:2.509ex;" alt="{\displaystyle n=1,2,3,\dots }" loading="lazy"> these numbers of trees are

<div class="block-indent" style="padding-left: 1.6em;">1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (sequence <a href="https://oeis.org/A000108" class="extiw external" title="oeis:A000108">A000108</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</div>

Thus, if one of these trees is selected uniformly at random, its probability is the <a href="Multiplicative_inverse" title="Multiplicative inverse">reciprocal</a> of a Catalan number. Trees generated from a model in this distribution are sometimes called random binary Catalan trees.<a href="#cite_note-FOOTNOTESedgewickFlajolet2013287-14">[14]</a> They have expected depth proportional to the square root of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, rather than to the logarithm.<a href="#cite_note-FOOTNOTEKnuth200515-15">[15]</a> More precisely, the expected depth of a randomly chosen node in an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-node tree of this type is

<msqrt>

</msqrt>

</mrow>

<mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)}</annotation>

</semantics>

</math><img src="./1f7e4d2307877bee5ba7e8473c4db4a108ab8ca6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:21.254ex; height:6.509ex;" alt="{\displaystyle {\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)}" loading="lazy">.<a href="#cite_note-FOOTNOTESedgewickFlajolet2013288-16">[16]</a></div>

The expected <a href="Strahler_number" title="Strahler number">Strahler number</a> of a uniformly random <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-node binary tree is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{4}n+O(1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{4}n+O(1)}</annotation>

</semantics>

</math><img src="./a5e79ded0e68389cc1961acbd1fba361a849289f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.393ex; height:2.843ex;" alt="{\displaystyle \log _{4}n+O(1)}" loading="lazy">, lower than the expected Strahler number of random binary search trees.<a href="#cite_note-FOOTNOTEDevroyeKruszewski1995-17">[17]</a>

Due to their large heights, this model of equiprobable random trees is not generally used for binary search trees. However, it has other applications, including:

<ul><li>Modeling the <a href="Parse_tree" title="Parse tree">parse trees</a> of <a href="Expression_(mathematics)" title="Expression (mathematics)">algebraic expressions</a> in <a href="Compiler" title="Compiler">compiler</a> design.<a href="#cite_note-FOOTNOTEMahmoud199263-18">[18]</a> Here the internal nodes of the tree represent <a href="Binary_operation" title="Binary operation">binary operations</a> in an expression and the external nodes represent the variables or constants on which the expressions operate. The bound on Strahler number translates into the <a href="Register_allocation" title="Register allocation">number of registers</a> needed to evaluate an expression.<a href="#cite_note-FOOTNOTEFlajoletRaoultVuillemin1979-19">[19]</a></li>

<li>Modeling <a href="Drainage_system_(geomorphology)" title="Drainage system (geomorphology)">river networks</a>, the original application for which the Strahler number was developed.<a href="#cite_note-FOOTNOTEShreve1966-20">[20]</a></li>

<li>Modeling possible <a href="Evolutionary_tree" class="mw-redirect" title="Evolutionary tree">evolutionary trees</a> for a fixed number of species. In this application, an extended binary tree is used, with the species at its external nodes.<a href="#cite_note-FOOTNOTEAldous1996-21">[21]</a></li></ul>

An algorithm of Jean-Luc Rémy generates a uniformly random binary tree of a specified size in time linear in the size, by the following process. Start with a tree consisting of a single external node. Then, while the current tree has not reached the target size, repeatedly choose one of its nodes (internal or external) uniformly at random. Replace the chosen node by a new internal node, having the chosen node as one of its children (equally likely left or right), and having a new external node as its other child. Stop when the target size is reached.<a href="#cite_note-22">[22]</a>

<div class="mw-heading mw-heading2"><h2 id="Branching_processes">Branching processes</h2></div>

The <a href="Galton%E2%80%93Watson_process" title="Galton–Watson process">Galton–Watson process</a> describes a family of distributions on trees in which the number of children at each node is chosen randomly, independently of other nodes. For binary trees, two versions of the Galton–Watson process are in use, differing only in whether an extended binary tree with only one node, an external root node, is allowed:

<ul><li>In the version where the root node may be external, it is chosen to be internal with some specified probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> or external with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-p}</annotation>

</semantics>

</math><img src="./9633a8692121eedfa99cace406205e5d1511ef8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.172ex; height:2.509ex;" alt="{\displaystyle 1-p}" loading="lazy">. If it is internal, its two children are trees generated recursively by the same process.</li>

<li>In the version where the root node must be internal, its left and right children are determined to be internal with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> or external with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-p}</annotation>

</semantics>

</math><img src="./9633a8692121eedfa99cace406205e5d1511ef8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.172ex; height:2.509ex;" alt="{\displaystyle 1-p}" loading="lazy">, independently of each other. In the case where they are internal, they are the roots of trees that are generated recursively by the same process.</li></ul>

Trees generated in this way have been called binary Galton–Watson trees. In the special case where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy"> they are called critical binary Galton–Watson trees.<a href="#cite_note-FOOTNOTEBurdWaymireWinn2000-23">[23]</a>

<div class="mw-heading mw-heading3"><h3 id="Analysis">Analysis</h3></div>

The probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy"> marks a <a href="Phase_transition" title="Phase transition">phase transition</a> for the binary Galton–Watson process: for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\leq {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\leq {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./23da90e2ad5cf9ba4b7d76effb2f5463a82ee5d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p\leq {\tfrac {1}{2}}}" loading="lazy"> the resulting tree is <a href="Almost_certainly" class="mw-redirect" title="Almost certainly">almost certainly</a> finite, whereas for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p>{\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p>{\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./0240c82158a2f52bc0eaf63e469679fd3bfb76ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p>{\tfrac {1}{2}}}" loading="lazy"> it is infinite with positive probability. More precisely, for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, the probability that the tree remains finite is

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}}</annotation>

</semantics>

</math><img src="./6df779337b95ec127c151e69f3f880669e63e801.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:15.953ex; height:6.176ex;" alt="{\displaystyle \displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}}" loading="lazy">.<a href="#cite_note-extinction-24">[24]</a></div>

Another way to generate the same trees is to make a sequence of <a href="Coin_flip" class="mw-redirect" title="Coin flip">coin flips</a>, with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> of heads and probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-p}</annotation>

</semantics>

</math><img src="./9633a8692121eedfa99cace406205e5d1511ef8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.172ex; height:2.509ex;" alt="{\displaystyle 1-p}" loading="lazy"> of tails, until the first flip at which the number of tails exceeds the number of heads (for the model in which an external root is allowed) or exceeds one plus the number of heads (when the root must be internal), and then use this sequence of coin flips to determine the choices made by the recursive generation process, in depth-first order.<a href="#cite_note-25">[25]</a>

Because the number of internal nodes equals the number of heads in this coin flip sequence, all trees with a given number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> of nodes are generated from (unique) coin flip sequences of the same length, and are equally likely, regardless of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">. That is, the choice of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> affects the variation in the size of trees generated by this process, but for a given size the trees are generated uniformly at random.<a href="#cite_note-26">[26]</a> For values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> below the critical probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy">, smaller values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> will produce trees with a smaller <a href="Expected_value" title="Expected value">expected</a> size, while larger values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> will produce trees with a larger expected size. At the critical probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy"> there is no finite bound on the expected size of trees generated by this process. More precisely, for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, the expected number of nodes at depth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> in the tree is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2p)^{i}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2p)^{i}}</annotation>

</semantics>

</math><img src="./8d4d8cda8035cb658ae9fec5e03f18d2d166d74b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.941ex; height:3.176ex;" alt="{\displaystyle (2p)^{i}}" loading="lazy">, and the expected size of the tree can be obtained by summing the expected numbers of nodes at each depth. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p<{\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p<{\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./45171449c124a53ca69150e1109e6cac180d446c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p<{\tfrac {1}{2}}}" loading="lazy"> this gives a <a href="Geometric_series" title="Geometric series">geometric series</a>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}}</annotation>

</semantics>

</math><img src="./bff6de0c6063258002ac4a1c8ead880ccb5aef53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:32.013ex; height:5.676ex;" alt="{\displaystyle \displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}}" loading="lazy">,</div>

for the expected tree size, but for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy"> this gives <a href="1_%2B_1_%2B_1_%2B_1_%2B_%E2%8B%AF" title="1 + 1 + 1 + 1 + ⋯">1 + 1 + 1 + 1 + ⋯</a>, a <a href="Divergent_series" title="Divergent series">divergent series</a>.<a href="#cite_note-27">[27]</a>

For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p={\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p={\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./65a18fde17cf506242214406888b4a5975708380.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; margin-left: -0.089ex; width:6.015ex; height:3.509ex;" alt="{\displaystyle p={\tfrac {1}{2}}}" loading="lazy">, any particular tree with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> internal nodes is generated with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/2^{2n+1}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/2^{2n+1}}</annotation>

</semantics>

</math><img src="./63fa9b39b7cbc99501df7deed2b45a23748895e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.628ex; height:3.176ex;" alt="{\displaystyle 1/2^{2n+1}}" loading="lazy">, and the probability that a random tree has this size is this probability multiplied by a Catalan number,

<mfrac>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle }</annotation>

</semantics>

</math><img src="./8d720d2c37205e21566f1041b39cbbbcf6c8269f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:45.6ex; height:6.509ex;" alt="{\displaystyle {\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle }" loading="lazy">.<a href="#cite_note-28">[28]</a></div>

<div class="mw-heading mw-heading3"><h3 id="Applications">Applications</h3></div>

Galton–Watson processes were originally developed to study the spread and extinction of human <a href="Surname" title="Surname">surnames</a>, and have been widely applied more generally to the dynamics of human or animal populations. These processes have been generalized to models where the probability of being an internal or external node at a given level of the tree (a generation, in the <a href="Population_dynamics" title="Population dynamics">population dynamics</a> application) is not fixed, but depends on the number of nodes at the previous level.<a href="#cite_note-FOOTNOTEJagers2011-29">[29]</a> A version of this process, with the critical probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./edef8290613648790a8ac1a95c2fb7c3972aea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}}" loading="lazy">, has been studied as a model for <a href="Speciation" title="Speciation">speciation</a>, where it is known as the critical branching process. In this process, each species has an <a href="Exponential_distribution" title="Exponential distribution">exponentially distributed</a> lifetime, and over the course of its lifetime produces child species at a rate equal to the lifetime. When a child is produced, the parent continues as the left branch of the evolutionary tree, and the child becomes the right branch.<a href="#cite_note-FOOTNOTEPopovic2004-30">[30]</a>

Another application of critical Galton–Watson trees (in the version where the root must be internal) arises in the <a href="Karger's_algorithm#Karger–Stein_algorithm" title="Karger's algorithm">Karger–Stein algorithm</a> for finding <a href="Minimum_cut" title="Minimum cut">minimum cuts</a> in graphs, using a recursive <a href="Edge_contraction" title="Edge contraction">edge contraction</a> process. This algorithm calls itself twice recursively, with each call having probability at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}}</annotation>

</semantics>

</math><img src="./edef8290613648790a8ac1a95c2fb7c3972aea2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.658ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}}" loading="lazy"> of preserving the correct solution value. The random tree models the subtree of correct recursive calls. The algorithm succeeds on a graph of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vertices whenever this random tree of correct recursive calls has a branch of depth at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\log _{2}n}</annotation>

</semantics>

</math><img src="./832e6fc50367578fee4c8b0a8a2fdd35e20c3044.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.357ex; height:2.676ex;" alt="{\displaystyle 2\log _{2}n}" loading="lazy">, reaching the base case of its recursion. The success probability is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (1/\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (1/\log n)}</annotation>

</semantics>

</math><img src="./ce2bcbd266651cfd4e3bc83dab01f7217c71d5be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.953ex; height:2.843ex;" alt="{\displaystyle \Omega (1/\log n)}" loading="lazy">, producing one of the logarithmic factors in the algorithm's <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2}\log ^{3}n)}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2}\log ^{3}n)}</annotation>

</semantics>

</math><img src="./b7ea30671eb6c2b806a4e945255c6c020afe5b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.226ex; height:3.176ex;" alt="{\displaystyle O(n^{2}\log ^{3}n)}" loading="lazy"> runtime.<a href="#cite_note-FOOTNOTEKargerStein1996-31">[31]</a>

<div class="mw-heading mw-heading3"><h3 id="Yule_process">Yule process</h3></div>

Devroye and Robson consider a related continuous-time random process in which each external node is eventually replaced by an internal node with two external children, at an exponentially distributed time after its first appearance as an external node. The number of external nodes in the tree, at any time, is modeled by a <a href="Simple_birth_process" class="mw-redirect" title="Simple birth process">simple birth process</a> or Yule process in which the members of a population give birth at a constant rate: giving birth to one child, in the Yule process, corresponds to being replaced by two children, in Devroye and Robson's model. If this process is stopped at any fixed time, the result is a binary tree of a random size (depending on the <a href="Stopping_time" title="Stopping time">stopping time</a>), distributed according to the random permutation model for that size. Devroye and Robson use this model as part of an algorithm to quickly generate trees in the random permutation model, described by their numbers of nodes at each depth rather than by their exact structure.<a href="#cite_note-FOOTNOTEDevroyeRobson1995-32">[32]</a> A discrete variant of this process starts with a tree consisting of a single external node, and repeatedly replaces a randomly-chosen external node by an internal node with two external children. Again, if this is stopped at a fixed time (with a fixed size), the resulting tree is distributed according to the random permutation model for that size.<a href="#cite_note-FOOTNOTEDrmota200919-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Binary_tries">Binary tries</h2></div>

Another form of binary tree, the binary <a href="Trie" title="Trie">trie</a> or digital search tree, has a collection of binary numbers labeling some of its external nodes. The internal nodes of the tree represent <a href="Prefix_(computer_science)" class="mw-redirect" title="Prefix (computer science)">prefixes</a> of their binary representations that are shared by two or more of the numbers. The left and right children of an internal node are obtained by extending the corresponding prefix by one more bit, a zero or a one bit respectively. If this extension does not match any of the given numbers, or it matches only one of them, the result is an external node; otherwise it is another internal node. Random binary tries have been studied, for instance for sets of random <a href="Real_number" title="Real number">real numbers</a> generated independently in the <a href="Unit_interval" title="Unit interval">unit interval</a>. Despite the fact that these trees may have some empty external nodes, they tend to be better balanced than random binary search trees. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> uniformly random real numbers in the unit interval, or more generally for any <a href="Square-integrable_function" title="Square-integrable function">square-integrable</a> probability distribution on the unit interval, the average depth of a node is asymptotically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation>

</semantics>

</math><img src="./d74677fc45e0d926639433586327cbc2982eae89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}" loading="lazy">, and the average height of the whole tree is asymptotically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\log _{2}n}</annotation>

</semantics>

</math><img src="./832e6fc50367578fee4c8b0a8a2fdd35e20c3044.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.357ex; height:2.676ex;" alt="{\displaystyle 2\log _{2}n}" loading="lazy">. The analysis of these trees can be applied to the <a href="Computational_complexity" title="Computational complexity">computational complexity</a> of trie-based <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a>.<a href="#cite_note-FOOTNOTEDevroye1984-33">[33]</a>

A variant of the trie, the <a href="Radix_tree" title="Radix tree">radix tree</a> or compressed trie, eliminates empty external nodes and their parent internal nodes. The remaining internal nodes correspond to prefixes for which both possible extensions, by a zero or a one bit, are used by at least one of the randomly chosen numbers. For a radix tree for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> uniformly distributed binary numbers, the shortest leaf-root path has length

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}n-\log _{2}\log n+o(\log \log n)}</annotation>

</semantics>

</math>

and the longest leaf-root path has length

<msub>

</mrow>

</msub>

<msqrt>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}n+{\sqrt {2\log _{2}n}}+o({\sqrt {\log n}}),}</annotation>

</semantics>

</math>

both <a href="With_high_probability" title="With high probability">with high probability</a>.<a href="#cite_note-FOOTNOTEDevroye1992-34">[34]</a>

<div class="mw-heading mw-heading2"><h2 id="Random_split_trees">Random split trees</h2></div>

<a href="Luc_Devroye" title="Luc Devroye">Luc Devroye</a> and <a href="Paul_Kruszewski" title="Paul Kruszewski">Paul Kruszewski</a> describe a recursive process for constructing random binary trees with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes. It generates a real-valued random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in the unit interval <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (0,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (0,1)}</annotation>

</semantics>

</math><img src="./c79c6838e423c1ed3c7ea532a56dc9f9dae8290b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (0,1)}" loading="lazy">, assigns the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xn}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xn}</annotation>

</semantics>

</math><img src="./d3ab0bb54d07c8020f6f14611e02700a0fcc4dd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.724ex; height:1.676ex;" alt="{\displaystyle xn}" loading="lazy"> nodes (rounded down to an integer number of nodes) to the left subtree, the next node to the root, and the remaining nodes to the right subtree. Then, it continues recursively using the same process in the left and right subtrees. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is chosen uniformly at random in the interval, the result is the same as the random binary search tree generated by a random permutation of the nodes, as any node is equally likely to be chosen as root. However, this formulation allows other distributions to be used instead. For instance, in the uniformly random binary tree model, once a root is fixed each of its two subtrees must also be uniformly random, so the uniformly random model may also be generated by a different choice of distribution (depending on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">) for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. As they show, by choosing a <a href="Beta_distribution" title="Beta distribution">beta distribution</a> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and by using an appropriate choice of shape to draw each of the branches, the mathematical trees generated by this process can be used to create realistic-looking botanical trees.<a href="#cite_note-FOOTNOTEDevroyeKruszewski1996-35">[35]</a>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-FOOTNOTEDrmota200919-1">^ <a href="#cite_ref-FOOTNOTEDrmota200919_1-0">a</a> <a href="#cite_ref-FOOTNOTEDrmota200919_1-1">b</a> <a href="#CITEREFDrmota2009">Drmota (2009)</a>, p. 19.

</li>

<li id="cite_note-FOOTNOTEKnuth1997-2"><a href="#cite_ref-FOOTNOTEKnuth1997_2-0">^</a> <a href="#CITEREFKnuth1997">Knuth (1997)</a>.

</li>

<li id="cite_note-FOOTNOTEKnuth1973-3"><a href="#cite_ref-FOOTNOTEKnuth1973_3-0">^</a> <a href="#CITEREFKnuth1973">Knuth (1973)</a>.

</li>

<li id="cite_note-FOOTNOTEVuillemin1980-4"><a href="#cite_ref-FOOTNOTEVuillemin1980_4-0">^</a> <a href="#CITEREFVuillemin1980">Vuillemin (1980)</a>.

</li>

<li id="cite_note-FOOTNOTESedgewickFlajolet2013286-5">^ <a href="#cite_ref-FOOTNOTESedgewickFlajolet2013286_5-0">a</a> <a href="#cite_ref-FOOTNOTESedgewickFlajolet2013286_5-1">b</a> <a href="#CITEREFSedgewickFlajolet2013">Sedgewick & Flajolet (2013)</a>, p. 286.

</li>

<li id="cite_note-FOOTNOTEMorin2014-6"><a href="#cite_ref-FOOTNOTEMorin2014_6-0">^</a> <a href="#CITEREFMorin2014">Morin (2014)</a>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFHibbard1962">Hibbard (1962)</a>; <a href="#CITEREFKnuth1973">Knuth (1973)</a>; <a href="#CITEREFMahmoud1992">Mahmoud (1992)</a>, p. 75.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFRobson1979">Robson (1979)</a>; <a href="#CITEREFPittel1985">Pittel (1985)</a>; <a href="#CITEREFDevroye1986">Devroye (1986)</a>; <a href="#CITEREFMahmoud1992">Mahmoud (1992)</a>, pp. 91–99; <a href="#CITEREFReed2003">Reed (2003)</a>.

</li>

<li id="cite_note-FOOTNOTEBrownShubert1984-9"><a href="#cite_ref-FOOTNOTEBrownShubert1984_9-0">^</a> <a href="#CITEREFBrownShubert1984">Brown & Shubert (1984)</a>.

</li>

<li id="cite_note-FOOTNOTEKruszewski1999-10"><a href="#cite_ref-FOOTNOTEKruszewski1999_10-0">^</a> <a href="#CITEREFKruszewski1999">Kruszewski (1999)</a>.

</li>

<li id="cite_note-treap-11">^ <a href="#cite_ref-treap_11-0">a</a> <a href="#cite_ref-treap_11-1">b</a> <a href="#CITEREFMartínezRoura1998">Martínez & Roura (1998)</a>; <a href="#CITEREFSeidelAragon1996">Seidel & Aragon (1996)</a>; <a href="#CITEREFMorin2014">Morin (2014)</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFTarjanLevyTimmel2021">Tarjan, Levy & Timmel (2021)</a>; <a href="#CITEREFGilaGoodrichTarjan2023">Gila, Goodrich & Tarjan (2023)</a>.

</li>

<li id="cite_note-FOOTNOTEDrmota200926-13"><a href="#cite_ref-FOOTNOTEDrmota200926_13-0">^</a> <a href="#CITEREFDrmota2009">Drmota (2009)</a>, p. 26.

</li>

<li id="cite_note-FOOTNOTESedgewickFlajolet2013287-14"><a href="#cite_ref-FOOTNOTESedgewickFlajolet2013287_14-0">^</a> <a href="#CITEREFSedgewickFlajolet2013">Sedgewick & Flajolet (2013)</a>, p. 287.

</li>

<li id="cite_note-FOOTNOTEKnuth200515-15"><a href="#cite_ref-FOOTNOTEKnuth200515_15-0">^</a> <a href="#CITEREFKnuth2005">Knuth (2005)</a>, p. 15.

</li>

<li id="cite_note-FOOTNOTESedgewickFlajolet2013288-16"><a href="#cite_ref-FOOTNOTESedgewickFlajolet2013288_16-0">^</a> <a href="#CITEREFSedgewickFlajolet2013">Sedgewick & Flajolet (2013)</a>, p. 288.

</li>

<li id="cite_note-FOOTNOTEDevroyeKruszewski1995-17"><a href="#cite_ref-FOOTNOTEDevroyeKruszewski1995_17-0">^</a> <a href="#CITEREFDevroyeKruszewski1995">Devroye & Kruszewski (1995)</a>.

</li>

<li id="cite_note-FOOTNOTEMahmoud199263-18"><a href="#cite_ref-FOOTNOTEMahmoud199263_18-0">^</a> <a href="#CITEREFMahmoud1992">Mahmoud (1992)</a>, p. 63.

</li>

<li id="cite_note-FOOTNOTEFlajoletRaoultVuillemin1979-19"><a href="#cite_ref-FOOTNOTEFlajoletRaoultVuillemin1979_19-0">^</a> <a href="#CITEREFFlajoletRaoultVuillemin1979">Flajolet, Raoult & Vuillemin (1979)</a>.

</li>

<li id="cite_note-FOOTNOTEShreve1966-20"><a href="#cite_ref-FOOTNOTEShreve1966_20-0">^</a> <a href="#CITEREFShreve1966">Shreve (1966)</a>.

</li>

<li id="cite_note-FOOTNOTEAldous1996-21"><a href="#cite_ref-FOOTNOTEAldous1996_21-0">^</a> <a href="#CITEREFAldous1996">Aldous (1996)</a>.

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <a href="#CITEREFRémy1985">Rémy (1985)</a>; <a href="#CITEREFMäkinenSiltaneva2003">Mäkinen & Siltaneva (2003)</a>; <a href="#CITEREFKnuth2005">Knuth (2005)</a>, pp. 16–17.

</li>

<li id="cite_note-FOOTNOTEBurdWaymireWinn2000-23"><a href="#cite_ref-FOOTNOTEBurdWaymireWinn2000_23-0">^</a> <a href="#CITEREFBurdWaymireWinn2000">Burd, Waymire & Winn (2000)</a>.

</li>

<li id="cite_note-extinction-24"><a href="#cite_ref-extinction_24-0">^</a> This is a special case of a general theorem about criticality and extinction probabilities in Galton–Watson processes, according to which the extinction probability is the smallest positive root of the formula <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(r)=r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(r)=r}</annotation>

</semantics>

</math><img src="./73367156f053b0cf30a80d9afb514cfc792b0c9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.121ex; height:2.843ex;" alt="{\displaystyle g(r)=r}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> is the <a href="Probability-generating_function" title="Probability-generating function">probability-generating function</a> of the distribution on the number of children, here <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)=(1-p)+px^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)=(1-p)+px^{2}}</annotation>

</semantics>

</math><img src="./112f69951b2a77a07633879e9c290d1e8bcef149.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.729ex; height:3.176ex;" alt="{\displaystyle g(x)=(1-p)+px^{2}}" loading="lazy">. See e.g. <a href="#CITEREFJagers2011">Jagers (2011)</a>, Theorem 2.1, p. 92. Jagers carries out the calculation of this root for the binary case on p. 97.

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> For the connection between trees and random walks (as generated by random coin flips) see e.g. Section 6, "Walks and trees" pp. 483–486, of <a href="#CITEREFHarris1952">Harris (1952)</a>.

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <a href="#CITEREFBroutinDevroyeFraiman2020">Broutin, Devroye & Fraiman (2020)</a>. More generally, every Galton–Watson process, conditioned on producing trees of a certain size, produces the same probability distribution as a critical Galton–Watson process: see section 2 of <a href="#CITEREFKennedy1975">Kennedy (1975)</a>.

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> For the expected number of nodes at each level of the tree, see e.g. <a href="#CITEREFAthreyaNey1972">Athreya & Ney (1972)</a>, Section I.A.2: Moments, p. 4.

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> By the equivalence between trees and random walks, this is the same as the probability of first returning to zero after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n+2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n+2}</annotation>

</semantics>

</math><img src="./2605e13cf9776ba0b511e395b804e8105efab862.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n+2}" loading="lazy"> steps in a <a href="Simple_random_walk" class="mw-redirect" title="Simple random walk">simple random walk</a>, for which see e.g. <a href="#CITEREFBertin2021">Bertin (2021)</a>, 2.5.1 Statistics of First Return Times to the Origin of a Random Walk, pp. 70–72.

</li>

<li id="cite_note-FOOTNOTEJagers2011-29"><a href="#cite_ref-FOOTNOTEJagers2011_29-0">^</a> <a href="#CITEREFJagers2011">Jagers (2011)</a>.

</li>

<li id="cite_note-FOOTNOTEPopovic2004-30"><a href="#cite_ref-FOOTNOTEPopovic2004_30-0">^</a> <a href="#CITEREFPopovic2004">Popovic (2004)</a>.

</li>

<li id="cite_note-FOOTNOTEKargerStein1996-31"><a href="#cite_ref-FOOTNOTEKargerStein1996_31-0">^</a> <a href="#CITEREFKargerStein1996">Karger & Stein (1996)</a>.

</li>

<li id="cite_note-FOOTNOTEDevroyeRobson1995-32"><a href="#cite_ref-FOOTNOTEDevroyeRobson1995_32-0">^</a> <a href="#CITEREFDevroyeRobson1995">Devroye & Robson (1995)</a>.

</li>

<li id="cite_note-FOOTNOTEDevroye1984-33"><a href="#cite_ref-FOOTNOTEDevroye1984_33-0">^</a> <a href="#CITEREFDevroye1984">Devroye (1984)</a>.

</li>

<li id="cite_note-FOOTNOTEDevroye1992-34"><a href="#cite_ref-FOOTNOTEDevroye1992_34-0">^</a> <a href="#CITEREFDevroye1992">Devroye (1992)</a>.

</li>

<li id="cite_note-FOOTNOTEDevroyeKruszewski1996-35"><a href="#cite_ref-FOOTNOTEDevroyeKruszewski1996_35-0">^</a> <a href="#CITEREFDevroyeKruszewski1996">Devroye & Kruszewski (1996)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin refbegin-columns references-column-width" style="column-width: 30em">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAldous1996" class="citation cs2"><a href="David_Aldous" title="David Aldous">Aldous, David</a> (1996), "Probability distributions on cladograms", in Aldous, David; Pemantle, Robin (eds.), <a rel="nofollow" class="external text" href="https://www.stat.berkeley.edu/~aldous/Papers/me69.ps">Random Discrete Structures</a>, The IMA Volumes in Mathematics and its Applications, vol. 76, Springer-Verlag, pp. 1–18, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4612-0719-1_1">10.1007/978-1-4612-0719-1_1</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4612-6881-9</bdi></cite></li>

<li><cite id="CITEREFAthreyaNey1972" class="citation cs2">Athreya, Krishna B.; Ney, Peter E. (1972), Branching Processes, Berlin: Springer-Verlag, pp. 199–206, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-65371-1">10.1007/978-3-642-65371-1</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-65371-1</bdi></cite></li>

<li><cite id="CITEREFBertin2021" class="citation cs2">Bertin, Eric (2021), Statistical Physics of Complex Systems: A Concise Introduction, Springer Series in Synergetics (3rd ed.), Springer International Publishing, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2021spcs.book.....B">2021spcs.book.....B</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-79949-6">10.1007/978-3-030-79949-6</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783030799496</bdi></cite></li>

<li><cite id="CITEREFBrownShubert1984" class="citation cs2">Brown, Gerald G.; Shubert, Bruno O. (1984), <a rel="nofollow" class="external text" href="https://scholar.archive.org/work/3fjrwxwgsnhobasgfbv4rsvozu">"On random binary trees"</a>, <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>, 9: 43–65, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.9.1.43">10.1287/moor.9.1.43</a></cite></li>

<li><cite id="CITEREFBroutinDevroyeFraiman2020" class="citation cs2">Broutin, Nicolas; <a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a>; Fraiman, Nicolas (April 2020), <a rel="nofollow" class="external text" href="http://luc.devroye.org/Broutin-Devroye-Fraiman-GaltonWatsonMarkov-2020.pdf">"Recursive functions on conditional Galton–Watson trees"</a> (PDF), Random Structures & Algorithms, 57 (2), Wiley: 304–316, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1805.09425">1805.09425</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Frsa.20921">10.1002/rsa.20921</a></cite></li>

<li><cite id="CITEREFBurdWaymireWinn2000" class="citation cs2">Burd, Gregory A.; Waymire, Edward C.; Winn, Ronald D. (February 2000), <a rel="nofollow" class="external text" href="https://projecteuclid.org/journals/bernoulli/volume-6/issue-1/A-self-similar-invariance-of-critical-binary-Galton-Watson-trees/bj/1082665377.full">"A self-similar invariance of critical binary Galton–Watson trees"</a>, <a href="Bernoulli_(journal)" class="mw-redirect" title="Bernoulli (journal)">Bernoulli</a>, 6 (1): 1–21, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3318630">10.2307/3318630</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3318630">3318630</a></cite></li>

<li><cite id="CITEREFDevroye1984" class="citation cs2">Devroye, Luc (1984), <a rel="nofollow" class="external text" href="http://luc.devroye.org/devroye_1984_probabilistic_analysis_height_tries_complexity_triesort.pdf">"A probabilistic analysis of the height of tries and of the complexity of triesort"</a> (PDF), <a href="Acta_Informatica" title="Acta Informatica">Acta Informatica</a>, 21 (3): 229–237, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00264248">10.1007/BF00264248</a></cite></li>

<li><cite id="CITEREFDevroye1986" class="citation cs2"><a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a> (1986), <a rel="nofollow" class="external text" href="http://luc.devroye.org/devroye_1986_univ_a_note_on_the_height_of_binary_search_trees.pdf">"A note on the height of binary search trees"</a> (PDF), <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 33 (3): 489–498, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F5925.5930">10.1145/5925.5930</a></cite></li>

<li><cite id="CITEREFDevroye1992" class="citation cs2"><a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a> (January 1992), <a rel="nofollow" class="external text" href="http://luc.devroye.org/patricia1992.pdf">"A note on the probabilistic analysis of patricia trees"</a> (PDF), Random Structures & Algorithms, 3 (2): 203–214, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Frsa.3240030209">10.1002/rsa.3240030209</a></cite></li>

<li><cite id="CITEREFDevroyeKruszewski1995" class="citation cs2"><a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a>; <a href="Paul_Kruszewski" title="Paul Kruszewski">Kruszewski, Paul</a> (1995), <a rel="nofollow" class="external text" href="http://luc.devroye.org/hs-ebt.pdf">"A note on the Horton–Strahler number for random trees"</a> (PDF), <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 56 (2): 95–99, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2895%2900114-R">10.1016/0020-0190(95)00114-R</a></cite></li>

<li><cite id="CITEREFDevroyeKruszewski1996" class="citation cs2"><a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a>; <a href="Paul_Kruszewski" title="Paul Kruszewski">Kruszewski, Paul</a> (1996), <a rel="nofollow" class="external text" href="http://luc.devroye.org/gd95.pdf">"The botanical beauty of random binary trees"</a> (PDF), in Brandenburg, Franz J. (ed.), Graph Drawing: 3rd Int. Symp., GD'95, Passau, Germany, September 20–22, 1995, Lecture Notes in Computer Science, vol. 1027, Springer-Verlag, pp. 166–177, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0021801">10.1007/BFb0021801</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-60723-6</bdi></cite></li>

<li><cite id="CITEREFDevroyeRobson1995" class="citation cs2"><a href="Luc_Devroye" title="Luc Devroye">Devroye, Luc</a>; Robson, John Michael (December 1995), <a rel="nofollow" class="external text" href="http://luc.devroye.org/devroye_robson_1995_generation_random_binary_search_tree.pdf">"On the generation of random binary aearch trees"</a> (PDF), <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 24 (6): 1141–1156, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2Fs0097539792224954">10.1137/s0097539792224954</a></cite></li>

<li><cite id="CITEREFDrmota2009" class="citation cs2"><a href="Michael_Drmota" title="Michael Drmota">Drmota, Michael</a> (2009), Random Trees: An Interplay between Combinatorics and Probability, Springer-Verlag, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-211-75357-6">10.1007/978-3-211-75357-6</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-211-75355-2</bdi></cite></li>

<li><cite id="CITEREFFlajoletRaoultVuillemin1979" class="citation cs2"><a href="Philippe_Flajolet" title="Philippe Flajolet">Flajolet, P.</a>; Raoult, J. C.; <a href="Jean_Vuillemin" title="Jean Vuillemin">Vuillemin, J.</a> (1979), <a rel="nofollow" class="external text" href="https://core.ac.uk/download/pdf/82609425.pdf">"The number of registers required for evaluating arithmetic expressions"</a> (PDF), <a href="Theoretical_Computer_Science_(journal)" title="Theoretical Computer Science (journal)">Theoretical Computer Science</a>, 9 (1): 99–125, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2879%2990009-4">10.1016/0304-3975(79)90009-4</a></cite></li>

<li><cite id="CITEREFGilaGoodrichTarjan2023" class="citation cs2">Gila, Ofek; <a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (2023), "Zip-zip trees: making zip trees more balanced, biased, compact, or persistent", in <a href="Pat_Morin" title="Pat Morin">Morin, Pat</a>; <a href="Subhash_Suri" title="Subhash Suri">Suri, Subhash</a> (eds.), Algorithms and Data Structures – 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings, Lecture Notes in Computer Science, vol. 14079, Springer, pp. 474–492, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2307.07660">2307.07660</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-031-38906-1_31">10.1007/978-3-031-38906-1_31</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-031-38905-4</bdi></cite></li>

<li><cite id="CITEREFHarris1952" class="citation cs2">Harris, T. E. (1952), "First passage and recurrence distributions", <a href="Transactions_of_the_American_Mathematical_Society" title="Transactions of the American Mathematical Society">Transactions of the American Mathematical Society</a>, 73 (3): 471–486, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0002-9947-1952-0052057-2">10.1090/s0002-9947-1952-0052057-2</a></cite></li>

<li><cite id="CITEREFHibbard1962" class="citation cs2"><a href="Thomas_N._Hibbard" title="Thomas N. Hibbard">Hibbard, Thomas N.</a> (1962), "Some combinatorial properties of certain trees with applications to searching and sorting", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 9 (1): 13–28, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321105.321108">10.1145/321105.321108</a></cite></li>

<li><cite id="CITEREFJagers2011" class="citation cs2">Jagers, Peter (2011), "Extinction, persistence, and evolution", in Chalub, Fabio A. C. C.; Rodrigues, José Francisco (eds.), The Mathematics of Darwin's Legacy, Mathematics and Biosciences in Interaction, Basel: Birkhäuser, pp. 91–104, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-0348-0122-5_5">10.1007/978-3-0348-0122-5_5</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783034801225</bdi></cite></li>

<li><cite id="CITEREFKargerStein1996" class="citation cs2"><a href="David_Karger" title="David Karger">Karger, David R.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (1996), <a rel="nofollow" class="external text" href="https://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf">"A new approach to the minimum cut problem"</a> (PDF), <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 43 (4): 601, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F234533.234534">10.1145/234533.234534</a></cite></li>

<li><cite id="CITEREFKennedy1975" class="citation cs2">Kennedy, Douglas P. (1975), "The Galton–Watson process conditioned on the total progeny", <a href="Journal_of_Applied_Probability" class="mw-redirect" title="Journal of Applied Probability">Journal of Applied Probability</a>, 12 (4): 800–806, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3212730">10.2307/3212730</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3212730">3212730</a></cite></li>

<li><cite id="CITEREFKnuth1973" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1973), "6.2.2 Binary Tree Searching", <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming, Vol. III: Sorting and Searching</a>, Addison-Wesley, pp. 422–451</cite></li>

<li><cite id="CITEREFKnuth1997" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1997), "2.3.4.5 Path Length", <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming, Vol. I: Seminumerical Algorithms</a> (3rd ed.), Addison-Wesley, pp. 399–406</cite></li>

<li><cite id="CITEREFKnuth2005" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (2005), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230102051934/https://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz">"Draft of Section 7.2.1.6: Generating All Trees"</a>, <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>, vol. IV, archived from <a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz">the original</a> on 2023-01-02, retrieved 2009-03-31</cite></li>

<li><cite id="CITEREFKruszewski1999" class="citation cs2"><a href="Paul_Kruszewski" title="Paul Kruszewski">Kruszewski, Paul</a> (1999), "A note on the Horton–Strahler number for random binary search trees", <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>, 69 (1): 47–51, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0020-0190%2898%2900192-6">10.1016/S0020-0190(98)00192-6</a></cite></li>

<li><cite id="CITEREFMäkinenSiltaneva2003" class="citation cs2">Mäkinen, Erkki; Siltaneva, Jarmo (2003), "A note on Rémy's algorithm for generating random binary trees", Missouri Journal of Mathematical Sciences, 15 (2): 103–109, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.35834%2F2003%2F1502103">10.35834/2003/1502103</a></cite></li>

<li><cite id="CITEREFMahmoud1992" class="citation cs2">Mahmoud, Hosam M. (1992), Evolution of Random Search Trees, John Wiley & Sons</cite></li>

<li><cite id="CITEREFMartínezRoura1998" class="citation cs2">Martínez, Conrado; Roura, Salvador (1998), "Randomized binary search trees", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 45 (2): 288–323, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.243">10.1.1.17.243</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F274787.274812">10.1145/274787.274812</a></cite></li>

<li><cite id="CITEREFMorin2014" class="citation cs2"><a href="Pat_Morin" title="Pat Morin">Morin, Pat</a> (March 22, 2014), "Chapter 7: Random Binary Search Trees", <a rel="nofollow" class="external text" href="https://opendatastructures.org/ods-python.pdf">Open Data Structures (in pseudocode)</a> (PDF) (0.1Gβ ed.), pp. 145–164</cite></li>

<li><cite id="CITEREFPittel1985" class="citation cs2">Pittel, B. (1985), "Asymptotical growth of a class of random trees", <a href="Annals_of_Probability" title="Annals of Probability">Annals of Probability</a>, 13 (2): 414–427, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faop%2F1176993000">10.1214/aop/1176993000</a></cite></li>

<li><cite id="CITEREFPopovic2004" class="citation cs2">Popovic, Lea (November 2004), "Asymptotic genealogy of a critical branching process", <a href="Annals_of_Applied_Probability" title="Annals of Applied Probability">Annals of Applied Probability</a>, 14 (4), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0503577">math/0503577</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2F105051604000000486">10.1214/105051604000000486</a></cite></li>

<li><cite id="CITEREFReed2003" class="citation cs2"><a href="Bruce_Reed_(mathematician)" title="Bruce Reed (mathematician)">Reed, Bruce</a> (2003), "The height of a random binary search tree", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 50 (3): 306–332, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F765568.765571">10.1145/765568.765571</a></cite></li>

<li><cite id="CITEREFRémy1985" class="citation cs2 cs1-prop-foreign-lang-source">Rémy, Jean-Luc (1985), <a rel="nofollow" class="external text" href="https://www.numdam.org/item/ITA_1985__19_2_179_0/">"Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire"</a>, RAIRO Informatique théorique (in French), 19 (2): 179–195, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1051%2Fita%2F1985190201791">10.1051/ita/1985190201791</a></cite></li>

<li><cite id="CITEREFRobson1979" class="citation cs2">Robson, J. M. (1979), "The height of binary search trees", <a href="Australian_Computer_Journal" class="mw-redirect" title="Australian Computer Journal">Australian Computer Journal</a>, 11: 151–153</cite></li>

<li><cite id="CITEREFSeidelAragon1996" class="citation cs2"><a href="Raimund_Seidel" title="Raimund Seidel">Seidel, Raimund</a>; <a href="Cecilia_R._Aragon" title="Cecilia R. Aragon">Aragon, Cecilia R.</a> (1996), "Randomized search trees", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 16 (4–5): 464–497, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs004539900061">10.1007/s004539900061</a> (inactive 12 July 2025)</cite><code class="cs1-code">{{citation}}</code>: CS1 maint: DOI inactive as of July 2025 (link)</li>

<li><cite id="CITEREFSedgewickFlajolet2013" class="citation cs2"><a href="Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; <a href="Philippe_Flajolet" title="Philippe Flajolet">Flajolet, Philippe</a> (2013), "Chapter 6: Trees", An Introduction to the Analysis of Algorithms (2nd ed.), Addison-Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780133373486</bdi></cite></li>

<li><cite id="CITEREFShreve1966" class="citation cs2">Shreve, Ronald L. (January 1966), "Statistical law of stream numbers", <a href="The_Journal_of_Geology" title="The Journal of Geology">The Journal of Geology</a>, 74 (1): 17–37, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1966JG.....74...17S">1966JG.....74...17S</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1086%2F627137">10.1086/627137</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/30075174">30075174</a></cite></li>

<li><cite id="CITEREFTarjanLevyTimmel2021" class="citation cs2"><a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a>; Levy, Caleb C.; Timmel, Stephen (2021), "Zip trees", <a href="ACM_Transactions_on_Algorithms" title="ACM Transactions on Algorithms">ACM Transactions on Algorithms</a>, 17 (4): 34:1–34:12, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1806.06726">1806.06726</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3476830">10.1145/3476830</a></cite></li>

<li><cite id="CITEREFVuillemin1980" class="citation cs2"><a href="Jean_Vuillemin" title="Jean Vuillemin">Vuillemin, Jean</a> (1980), "A unifying look at data structures", <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>, 23 (4): 229–239, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F358841.358852">10.1145/358841.358852</a></cite></li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-20" href="https://en.wikipedia.org/wiki/?title=Random_binary_tree&oldid=1301613237">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>